namespace DefaultNamespace
{
    /**
     *
     * 给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。

    示例 1：
    
    输入: "babad"
    输出: "bab"
    注意: "aba" 也是一个有效答案。
    
    来源：力扣（LeetCode）
    链接：https://leetcode-cn.com/problems/longest-palindromic-substring
    著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
     */
    public class MaxPalindromeChildStr
    {
        
        /// <summary>
        /// 暴力解法
        /// </summary>
        /// <param name="s"></param>
        /// <returns></returns>
        public static string GetMaxLengthPalidrome(string s)
        {
            /**
             *1.找出该字符串的所有子字符串
             * 2.判断字符串是否为回文子串
             * 3.判断回文子串的最长 
             */
            string result = "";

            List<string> allStr = new List<string>();

            int strIndex = 0;
            while (strIndex < s.Length)
            {
                
                int endIndex = s.Length-strIndex;

                for (; endIndex > 0; endIndex--)
                {
                    allStr.Add(s.Substring(strIndex, endIndex));
                }
                strIndex++;
            }

            

            for (int i = 0; i < allStr.Count; i++)
            {
                if(IsPalidrome(allStr[i]))
                {
                    if (result.Length < allStr[i].Length)
                    {
                        result = allStr[i];
                    }
                }
            
            }
            
            return result;
        }

        private static bool IsPalidrome(string str)
        {
            int index = 0;

            int end = str.Length - 1;

            bool result = true;

            while (index <= end)
            {
                if (str[index] == str[end])
                {
                    index++;
                    end--;
                }
                else
                {
                    result = false;
                    break;
                }
            }

            return result;
        }
        
       
       	// 中心扩展法  以一个点  往两边展开 看两边是不是相同的
         public static string longestPalindrome(string s)
        {
            if (s == null || s.Length < 1)
            {
                return "";
            }

            int start = 0;  //切割字符串 开始位置
            int end = 0;  //结束位置
            for (int i = 0; i < s.Length; i++) {
                int len1 = expandAroundCenter(s, i, i); //判断奇数
                int len2 = expandAroundCenter(s, i, i + 1); //判断偶数的
                int len = Math.Max(len1, len2);
                if (len > end - start) {
                    start = i - (len - 1) / 2;  
                    end = i + len / 2; 
                }
            }
            return s.Substring(start, end-start+1);
        }
                
        private static int expandAroundCenter(string s, int left, int right) {
            int L = left, R = right;
            while (L >= 0 && R < s.Length && s[L] == s[R]) {
                L--;
                R++;
            }
            return R - L - 1;
        }
        
    }
}